package _interview150;

import java.util.*;

/**
 * 380. O(1) 时间插入、删除和获取随机元素
 */
public class No380 {
    private final Map<Integer, Integer> map;
    private final List<Integer> list;

    public No380() {
        map = new HashMap<>();
        list = new ArrayList<>();
    }

    public boolean insert(int val) {
        if (map.containsKey(val)) return false;
        map.put(val, list.size());
        list.add(val);
        return true;
    }

    public boolean remove(int val) {
        if (!map.containsKey(val)) return false;
        Integer i = map.get(val);
        list.set(i, list.get(list.size() - 1));
        map.put(list.get(list.size() - 1), i);
        list.remove(list.size() - 1);
        map.remove(val);
        return true;
    }

    public int getRandom() {
        return list.get((int) (Math.random() * list.size()));
    }
}
